|
In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers is a second sequence of numbers , the sums of prefixes (running totals) of the input sequence: : : : :... For instance, the prefix sums of the natural numbers are the triangular numbers: : Prefix sums are trivial to compute in sequential models of computation, by using the formula to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,〔.〕 and they form the basis of the scan higher-order function in functional programming languages. When datasets are stored in Fenwick trees, prefix sums can be calculated in O(log) time. Prefix sums of large datasets can be computed in using Fenwick tree. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.〔〔〔.〕 Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing. 〔.〕〔.〕 Mathematically, the operation of taking prefix sums can be generalized from finite to infinite sequences; in that context, a prefix sum is known as a partial sum of a series. Prefix summation or partial summation form linear operators on the vector spaces of finite or infinite sequences; their inverses are finite difference operators. ==Scan higher order function== In functional programming terms, the prefix sum may be generalized to any binary operation (not just the addition operation); the higher order function resulting from this generalization is called a scan, and it is closely related to the fold operation. Both the scan and the fold operations apply the given binary operation to the same sequence of values, but differ in that the scan returns the whole sequence of results from the binary operation, whereas the fold returns only the final result. For instance, the sequence of factorial numbers may be generated by a scan of the natural numbers using multiplication instead of addition: : In Haskell, there are two variants of scan, called scanl and scanl1, differing slightly in their argument signature, and the prefix sum operation may be written scanl1 (+). The corresponding suffix operations are also available as scanr and scanr1.〔.〕 The procedural Message Passing Interface libraries provide an operation MPI_Scan for computing a scan operation between networked processing units.The C++ language has a standard library function partial_sum; despite its name, it takes a binary operation as one of its arguments, and performs a scan with that operation.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「prefix sum」の詳細全文を読む スポンサード リンク
|